package com.captain.special.二叉树.中等;

import com.captain.leetcode.TreeNode;
import com.captain.leetcode.链表.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Des:
 *
 * @author XL
 * @Date 2022/5/16 18:04
 */
public class 有序链表转换二叉搜索树109 {
    List<Integer> arr;

    public TreeNode sortedListToBST(ListNode head) {
        arr = listArr(head);
        if (arr.size() == 0) {
            return new TreeNode();
        }
        return recur(0, arr.size() - 1);
    }

    public List<Integer> listArr(ListNode head) {
        List<Integer> res = new ArrayList<>();
        while (head != null) {
            res.add(head.val);
            head = head.next;
        }
        return res;
    }

    public TreeNode recur(int left, int right) {
        //1, 2, 3, 4, 5
        if (left > right) return null;
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(arr.get(mid));
        root.left = recur( left, mid - 1);
        root.right = recur( mid + 1, right);
        return root;
    }

    public static void main(String[] args) {
        System.out.println(1 / 2);
    }
}
